Content addressable memory (CAM) is being increasingly used in search engines today. It is a type of memory that in addition to allowing to perform read and write operations, it accepts data as input and returns an address as its output. This is in contrast to the normal memory, which only takes an address as an input and returns data stored at that address as an output.
A typical CAM contains, among other logic blocks: a CAM array block, a match detection block, and a priority encoder block. A CAM receives a data input, a data sample often termed a “word” (i.e., a plurality of bits or trits) even though its size is not standard and in current usage it is often quite long. The CAM array block contains CAM cells and comparison logic. The match detection block contains logics and sense amplifiers which determine if such a word being processed has any matches and produces a match signal for each content word compared against. The priority encoder block contains logics to process the set of match signals and to determine from it any matches of a received word are indicated, and to pick among all such matches to establish one as having priority according to a pre-established rule. The CAM then outputs the address of the highest priority match as a result output.
In the CAMs, as the wordlength (i.e., width) of a CAM entry increases, the capacitance of each CAM entry's match line generally also increases proportionately. This can result in reducing the reliability of detecting a match state because of a much smaller voltage change on a match line having a potentially large and entry-width dependent capacitance. The larger the match line's capacitance, the longer it will take to discharge in the case of mismatch entry, in turn requiring a longer detection period.
Therefore, when storage requirements exceed the number of entries (i.e., when the width increases) that may be stored on a single CAM, multiple CAMs are cascaded together to expand the number of search entries. Conventional techniques achieve the cascading of the CAMs by employing well known methods, which pipeline the match outputs of each CAM using flops or by increasing the hierarchy of match evaluations to connect a plurality of CAMs to facilitate searching as a single entry.
However, these techniques generally process outputs of each CAM instances which can result in requiring logic intensive post processing circuits that can be complex and produce irregular outputs. Further, these techniques can have a significant latency in generating a final search result. Furthermore, these techniques use hierarchical combination of local evaluation results which are slow in a precharge/evaluate scheme due to large interconnect lengths as the CAM size increases. Also, these techniques can require hierarchical evaluation which may result in limited width expansion even for reasonable speed targets. In addition, the hierarchical evaluation can require additional layout resources which can result in consuming more power switching long interconnects that may limit the number of CAMs that can be cascaded. Moreover, these techniques are only feasible to cascade a fewer number of CAMs. It is generally difficult to achieve such wordlengths using the current techniques in a single CAM.